/**
 * @file maze_clustering.js, an implementation for maze.js to generate a maze using clustering method.
 *
 * @author nobu <nobu@ctmk.amanek.jp>
 */

(function(define) {
define([], function() {
	/**
	* @constructor
	*/
	var Maze_Algorithm = function() {
		// initialize
	};
	
	/**
	 * Generate a maze.
	 *
	 * @return {Maze.Result}
	 * @param {Maze.Config} config
	 * @throw {RangeError} It will throw if any config option is invalid.
	 */
	Maze_Algorithm.generate = function (config) {
		return generate_using_clustering(config);
	};
	
	/**
	 * Signature of this method.
	 */
	Maze_Algorithm.Signature = function() {
		return "clustering";
	};

	return Maze_Algorithm;

	/**
	 * @class
	 */
	function Work(config) {
		if (config.need_process) {
			this.process = [];
		}
		this.data = [];
	}
	
	/**
	 * Generate a maze using clustering method.
	 * @return {Maze.Result}
	 * @param {Maze.Config} config
	 */
	function generate_using_clustering(config) {
		validate(config);
		work = new Work(config);

		work.data = Maze_Algorithm.get_data_filled(config.width, config.height, Maze_Algorithm.CellType.WALL);

		put_rooms(work, config.width, config.height);
		remove_walls(work, config.width, config.height);
		
		result = new Maze_Algorithm.Result(config, Maze_Algorithm.Signature());
		if (config.need_data) {
			result.data = work.data;
		}
		if (config.need_process) {
			result.process = work.process;
			result.celltype_to_fill = Maze_Algorithm.CellType.WALL;
		}
		return result;
	}
	
	/**
	 * @param {Maze.Config} config
	 */
	function validate(config) {
		if ((config.width < 3) || (config.width%2 === 0) || (config.height < 3) || (config.height%2 === 0)) {
			// A limitation in this algorithm.
			throw new RangeError("config.width and config.height must be at least 3 and be a odd number.");
		}
	}
	

	/**
	 * @param {Maze_Algorithm.Work} work
	 * @param {number} width
	 * @param {number} height
	 */
	function put_rooms(work, width, height) {
		var put_path = ('process' in work) ? function (work, x, y, id) { return Maze_Algorithm.put_with_process(work, x, y, id); } : function (work, x, y, id) { return Maze_Algorithm.put_without_process(work, x, y, id); };

		var id = 1;
		for (var y = 1; y < height-1; y += 2) {
			for (var x = 1; x < width-1; x += 2) {
				put_path(work, x, y, id);
				id += 1;
			}
		}
	}
	
	/**
	 * @param {Maze_Algorithm.Work} work
	 * @param {number} width
	 * @param {number} height
	 */
	function remove_walls(work, width, height) {
		var put_path = ('process' in work) ? function (work, x, y, id) { return Maze_Algorithm.put_with_process(work, x, y, id); } : function (work, x, y, id) { return Maze_Algorithm.put_without_process(work, x, y, id); };

		var candidates_to_remove = [];
		(function() {
			for (var y = 1; y < height-1; y += 1) {
				for (var x = 1+(y&0x1); x < width-1; x += 2) {
					candidates_to_remove.push({ x: x, y: y });
				}
			}
		})();
		candidates_to_remove = shuffle(candidates_to_remove);

		var neighbor, cluster_id;
		for (var i = 0; i < candidates_to_remove.length; i += 1) {
			var wall = candidates_to_remove[i];
			if (wall.y & 0x1) {
				neighbor = [work.data[wall.y][wall.x-1], work.data[wall.y][wall.x+1]];
			} else {
				neighbor = [work.data[wall.y-1][wall.x], work.data[wall.y+1][wall.x]];
			}
			if (neighbor[0] == neighbor[1]) {
				continue;
			}

			cluster_id = Math.min.apply(null, neighbor);
			put_path(work, wall.x, wall.y, cluster_id);
			join_cluster(work, wall.x, wall.y, cluster_id);
		}
	}
	
	/**
	 * @param {Maze_Algorithm.Work} work
	 * @param {number} x
	 * @param {number} y
	 * @param {number} id - cluster id.
	 */
	function join_cluster(work, x, y, id) {
		var put_path = function (work, x, y, id) { return Maze_Algorithm.put_without_process(work, x, y, id); };
		var nodes = [{ x: x, y: y }];
		while (nodes.length > 0) {
			var node = nodes.shift();
			for (var d = 0; d < 4; d += 1) {
				var dir = get_h_v(d);
				var n_x = node.x + dir.h;
				var n_y = node.y + dir.v;
				if ((work.data[n_y][n_x] == id) || (work.data[n_y][n_x] == Maze_Algorithm.CellType.WALL)) {
					continue;
				}
				work.data[n_y][n_x] = id;
				nodes.push({ x: n_x, y: n_y });
			}
		}
	}

	/**
	 * @param {number} d - direction.
	 * @return {{h: number, v:number}}
	 */
	function get_h_v(d) {
		//    d:  v  h  dir
		// 0x00:  0  1   >
		// 0x01:  0 -1   <
		// 0x10:  1  0   v
		// 0x11: -1  0   ^
		h = (((d & 0x2) >> 1)-1) & (1 - ((d & 0x1) << 1));
		v = (((~d & 0x2) >> 1)-1) & (1 - ((d & 0x1) << 1));
		return { h: h, v: v };
	}
	
	/**
	 * shuffle by Fisher-Yates.
	 * @param {Array} arr 
	 * @return {Array} 
	 */
	function shuffle(arr) {
		var i, j, temp;
		arr = arr.slice();
		i = arr.length;
		if (i === 0) {
			return arr;
		}
		while (--i) {
			j = Math.floor(Math.random() * (i + 1));
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
		return arr;
	}

});
})(typeof define !== 'undefined' ?
	// Use define for AMD if available
	define :
	// If no define, look for module to export as a CommonJS module.
	typeof module !== 'undefined' ?
	function(deps, factory) { module.exports = factory(); } :
	// If no define or module, attach to current context.
	typeof Maze !== 'undefined' ?
	function(deps, factory) { this.Maze.Clustering = factory(); } :
	function(deps, factory) { this.Maze_Clustering = factory(); }
);
